/*
 * Universidad del Valle de Guatemala
 * Algoritmos y Estructura de Datos
 * David Hsieh #08225
 */


import java.util.Scanner;

public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here

        String cadena;
        Scanner lector = new Scanner(System.in);
        ListaOrdenada lista;
        int f = 1;
        Nodo item;

        System.out.println("Ingrese su cadena de caracteres");
        cadena = lector.nextLine();
        lista = new ListaOrdenada(cadena.length());

        //Meter cada carecter a un nodo, y si es repetido incrementar frecuencia
        for(int i =0; i < cadena.length(); i++) {            
            Nodo query = new Nodo(cadena.charAt(i));
            item = lista.retirar(query);
            if (item == null) {
                lista.insertar(query);

           
            } else {
                item.incFrecuencia();
                lista.insertar(item);

            }


        }



     

        //Unir todos los nodos a un solo nodo (arbol)
        while(lista.getCantidad() > 1) {
            Nodo nodoTemp = new Nodo();
            int f1, f2;
            //String a, b;
            f1= lista.verPrimero().getFrecuencia() ;
            //a = ""+lista.verPrimero().getDato();
            nodoTemp.setIzquierdo(lista.retirar());
            f2 = lista.verPrimero().getFrecuencia();
            //b = ""+lista.verPrimero().getDato();
            nodoTemp.setDerecho(lista.retirar());
            nodoTemp.setFrecuencia(f1+f2);
            //nodoTemp.setDato(a+b);
            lista.insertar(nodoTemp);
        }

        lista.verPrimero().recorrer();

        

        




    }

}
